//给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。 
//
// 换句话说，s1 的排列之一是 s2 的 子串 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s1 = "ab" s2 = "eidbaooo"
//输出：true
//解释：s2 包含 s1 的排列之一 ("ba").
// 
//
// 示例 2： 
//
// 
//输入：s1= "ab" s2 = "eidboaoo"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s1.length, s2.length <= 104 
// s1 和 s2 仅包含小写字母 
// 
// Related Topics 哈希表 双指针 字符串 滑动窗口 
// 👍 399 👎 0

  
package com.zwy.leetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class PermutationInString{
    public static void main(String[] args) {
        Solution solution = new PermutationInString().new Solution();
        String s1="ab";
        String s2="eidboaoo";
        boolean b = solution.checkInclusion(s1, s2);
        System.out.println(b);
    }
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> map=new HashMap<>();
        Map<Character,Integer> map2=new HashMap<>();
        int length=s1.length();
        int length2=s2.length();
        if(length>length2)return false;
        for (int i = 0; i <=s2.length()-length; i++) {
            if(isInclusion(i,i+length,s1,s2,map,map2))return true;
        }
        return false;
    }
    public boolean isInclusion(int start,int end,String s1,String s2,Map<Character,Integer>map,Map<Character,Integer>map2){
        for (int i = start; i < end; i++) {
            if(!map.containsKey(s1.charAt(i-start))){
                map.put(s1.charAt(i-start),1);
            }
            else{
                map.put(s1.charAt(i-start),map.get(s1.charAt(i-start))+1);
            }
            if(!map2.containsKey(s2.charAt(i))){
                map2.put(s2.charAt(i),1);
            }
            else{
                map2.put(s2.charAt(i),map2.get(s2.charAt(i))+1);
            }
        }
        Set<Character> set = map.keySet();
        int b2=0;
        int b1=0;
        for (Character character : set) {
            b1=map.get(character);
           if(map2.containsKey(character))
             b2=map2.get(character);
            if(b1!=b2){
                map.clear();
                map2.clear();
                return false;
            }
            b1=0;
            b2=0;
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}